package hash

func isAngram(origin, target string) bool {
	if len(origin) != len(target) {
		return false
	}
	originMap := make(map[rune]int)
	for _, v := range origin {
		originMap[v]++
	}
	for _, v := range target {
		if _, ok := originMap[v]; !ok {
			return false
		}
		originMap[v]--
		if originMap[v] < 0 {
			return false
		}
	}
	for _, v := range originMap {
		if v != 0 {
			return false
		}
	}
	return true
}

func findAnagrams(s string, p string) []int {
	var res []int
	var sFreq, pFreq [26]int
	for _, ch := range p {
		pFreq[ch-'a']++
	}
	left, right := 0, 0
	for right < len(s) {
		// a +1
		// b +1
		// c +1
		sFreq[s[right]-'a']++
		if right-left+1 == len(p) {
			if sFreq == pFreq {
				res = append(res, left)
			}
			// a -1
			sFreq[s[left]-'a']--
			left++
		}
		// d +1
		right++
	}
	return res
}

func threeSum(nums []int) [][]int {
	var res [][]int
	for i := 0; i < len(nums)-2; i++ {
		for j := i + 1; j < len(nums)-1; j++ {
			for k := j + 1; k < len(nums); k++ {
				if nums[i]+nums[j]+nums[k] == 0 {
					res = append(res, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}
	return res
}

func fourNumberSum(nums []int, target int) [][]int {
	var res [][]int
	for i := 0; i < len(nums)-3; i++ {
		for j := i + 1; j < len(nums)-2; j++ {
			for k := j + 1; k < len(nums)-1; k++ {
				for l := k + 1; l < len(nums); l++ {
					if nums[i]+nums[j]+nums[k]+nums[l] == target {
						res = append(res, []int{nums[i], nums[j], nums[k], nums[l]})
					}
				}
			}
		}
	}
	return res
}
